The present invention generally relates to error handling in the field of communication systems and, more particularly, to decoding signals, which have been transmitted using error correction codes, using a maximum a posteriori (MAP) decoding technique.
The growth of commercial communication systems and, in particular, the explosive growth of cellular radiotelephone systems, have compelled system designers to search for ways to increase system capacity without reducing communication quality beyond consumer tolerance thresholds. One technique to achieve these objectives involved changing from systems, wherein analog modulation was used to impress data onto a carrier wave, to systems wherein digital modulation was used to impress the data on carrier waves.
In wireless digital communication systems, standardized air interfaces specify most of the system parameters, including modulation type, burst format, communication protocol, etc. For example, the European Telecommunication Standard Institute (ETSI) has specified a Global System for Mobile Communications (GSM) standard that uses time division multiple access (TDMA) to communicate control, voice and data information over radio frequency (RF) physical channels or links using a Gaussian Minimum Shift Keying (GMSK) modulation scheme at a symbol rate of 271 ksps. In the U.S., the Telecommunication Industry Association (TIA) has published a number of Interim Standards, such as IS-54 and IS-136, that define various versions of digital advanced mobile phone service (D-AMPS), a TDMA system that uses a differential quadrature phase shift keying (DQPSK) modulation scheme for communicating data over RF links.
TDMA systems subdivide the available frequency band into one or more RF channels, which are further divided into a number of physical channels corresponding to timeslots in TDMA frames. Logical channels are formed of one or several physical channels where modulation and coding is specified. In these systems, the mobile stations communicate with a plurality of scattered base stations by transmitting and receiving bursts of digital information over uplink and downlink RF channels.
The growing number of mobile stations in use today has generated the need for more voice and data channels within cellular telecommunication systems. As a result, base stations have become more closely spaced, with an increase in interference between mobile stations operating on the same frequency in neighboring or closely spaced cells. Although digital techniques provide a greater number of useful channels from a given frequency spectrum, there still remains a need to reduce interference, or more specifically to increase the ratio of the carrier signal strength to interference, (i.e., carrier-to-interference (C/I) ratio).
In order to provide various communication services, a corresponding minimum user bit rate is required. For example, for voice and/or data services, user bit rate corresponds to voice quality and/or data throughput, with a higher user bit rate producing better voice quality and/or higher data throughput. The total user bit rate is determined by a selected combination of techniques for speech coding, error correction (channel coding), modulation scheme and the number of assignable resources (e.g., codes, time slots, frequencies, etc.) per connection.
Of particular interest in this specification are error correction or channel codes. Digital communication systems employ various techniques to handle erroneously received information. Generally speaking, these techniques include those which aid a receiver to correct the erroneously received information, e.g., forward error correction (FEC) techniques, and those which enable the erroneously received information to be retransmitted to the receiver, e.g., automatic retransmission request (ARQ) techniques. FEC techniques include, for example, convolutional or block coding of the data prior to modulation, which coding is intended to permit the correction of errors introduced by noise and interference. FEC coding involves representing a certain number of data bits using a larger number of code bits. Thus, it is common to refer to convolutional codes by their code rates, e.g., 1/2 and 1/3, wherein the lower code rates provide greater error protection but lower user bit rates for a given channel bit rate.
At the receiver side, the received sequence is decoded to allow further processing of the data. Of course, the channel over which the signal has been transmitted makes this decoding process more challenging. This challenge is graphically depicted in FIG. 1. Therein, a stream of symbols u is input to a convolutional encoder 10. The encoded symbol stream x is transmitted over a transmission channel 12, e.g., over an air interface or a wireline, and received by a receiving entity as symbol stream y to reflect the impact of the channel on the transmitted signal. The MAP decoder 14 interprets the received symbol stream y to output symbol stream û, which is an estimate of the original symbol stream u. Note that in order to simplify this discussion, descriptions of various other processes which are well known in the art, e.g., the modulation and demodulation processes performed at the transmitter and receiver side, respectively, have been omitted.
The MAP decoding algorithm which can be employed in decoder 14, also known as the symbol-by-symbol Maximum-A-Posteriori algorithm or BCJR algorithm, was proposed by Bahl, Cocke, Jelinek and Raviv in xe2x80x9cOptimal Decoding of Linear Codes for Minimizing Symbol Error Ratexe2x80x9d, IEEE Trans. Inform. Theory, Vol. IT-20, pp.284-287, March 1974, the disclosure of which is incorporated here by reference. Variations on the MAP algorithm have also been proposed, which variations are more commercially feasible from an implementation point of view. For example, the Log-Map (processing performed in the logarithmic domain) and Max-Log-Map (a simplified version of Log-Map) algorithms have been described in the literature, e.g., xe2x80x9cIterative Decoding of Binary Block and Convolutional Codesxe2x80x9d, to Hagenauer et al., IEEE Trans. Inform. Theory, Vol. IT-42, pp. 429-445, March 1996, the disclosure of which is incorporated here by reference.
Due to their computational complexity and relatively moderate performance increases relative to less complex decoders (e.g., Viterbi decoders) under most conditions, MAP decoders have enjoyed relatively little popularity since their inception in the 1970""s. However, as the development of error correction coding has advanced, interest in MAP decoders has been rekindled as Shannon""s limit is approached. Those skilled in the art will appreciate that Shannon""s limit establishes the smallest ratio of energy per bit to single sided noise density (Eb/N0) for reliable transmission. Although Shannon proved this limit in the late 1940""s, error correction codes have still not been developed which provide this theoretically possible performance. However, a recent class of so-called xe2x80x9cturboxe2x80x9d codes comes much closer to operating at Shannon""s limit. With the advent of these, and other, new types of error correction codes, the MAP decoder has returned to prominence.
The detailed operation of the MAP algorithm is described below, and the metrics involved in the MAP algorithm will be more readily understood upon review of the equations found therein. One possible implementation of a MAP decoder is to simply provide a decoder which implements the MAP algorithm in a straightforward manner. That is, for a received sequence having N symbols, in a first step calculating and storing all of the branch transition metrics and the forward state metrics. After the Nth branch transition metric and Nth forward state metric have been calculated, then calculating all N reverse state metrics. Finally, after the reverse state metrics have been calculated, the likelihood ratios are calculated. However, the processing delay involved in such a straightforward implementation of the MAP decoding process is relatively high even when using powerful processors to perform the computations. Today""s communication systems demand higher and higher bitrates, and are less and less tolerant of processing delays.
One attempt found in the literature to reduce the processing delays associated with implementing the MAP algorithm is found in the disclosure of WO 98/20617 entitled xe2x80x9cSoft Decision Output Decoder for Decoding Convolutionally Encoded Codewordsxe2x80x9d, the disclosure of which is expressly incorporated here by reference. Therein, a Log-Map decoder is described wherein a first xe2x80x9cgeneralizedxe2x80x9d Viterbi decoder begins at an initial state t0 and provides a plurality of forward state metrics xcex1 for each state at each time interval over a window length 2L. A second xe2x80x9cgeneralizedxe2x80x9d Viterbi decoder is also provided which starts at a second time t2L and provides a plurality of reverse state metrics xcex2 for each state at each time interval. A processor then performs a dual maxima computation at each state using a forward state metric for a first state, a reverse state metric for a second state and the branch transition metric for the path between the first and second states.
Although this MAP decoding implementation may reduce the processing delay relative to a straightforward implementation of the MAP algorithm, it has a relatively high complexity and is suboptimal in the sense that initial estimates are used at each start of the second xe2x80x9cgeneralizedxe2x80x9d Viterbi decoder for calculating the reverse state metrics. Accordingly, it would be desirable to provide a MAP decoder implementation with reduced processing delay, with limited (if any) additional complexity and without resorting to suboptimal variations of the algorithm to enable efficient decoding of the powerful error correction codes which are being considered for next generation communication systems.
These and other drawbacks and limitations of conventional methods and systems for communicating information are overcome according to the present invention, the processing delay can be reduced (by, for example, a factor of approximately two relative to a straightfoward implementation) by implementing a decoder and decoding technique wherein the Forward State Metric Calculation (FSMC) and the Reverse State Metric Calculation (RSMC) are processed in parallel. Implementation complexity is also minimized relative to, e.g., WO98/20617 and can be further reduced by recognizing the processing timing associated with various tasks and eliminating unnecessary additional processing units, e.g., branch transition metric calculation units and likelihood ratio calculating units.